package org.xqh.study.leetcode.algorithm.linkedlist;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName RemoveNthFromEnd
 * @Description 删除链表的倒数第 N 个结点
 * <p>
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * @Author xuqianghui
 * @Date 2021/2/4 17:27
 * @Version 1.0
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        ListNode node = new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, new ListNode(8))))));
        ListNode result = removeNthFromEnd(node, 3);
        System.out.println(JSON.toJSONString(result));
    }

    /**
     * 用 快慢指针方法
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = null;//快指针
        for(int k = 0; k < n; k ++){
            first = first == null ? head : first.next;
        }
        ListNode second = head;//慢指针 (被删除节点)
        ListNode pre = null;//被删除节点 的前节点
        while (first.next != null){
            first = first.next;
            pre = second;
            second = second.next;
        }
        if(pre == null){
            return second.next;
        }
        pre.next = second.next;
        return head;
    }

    /**
     * 用list集合 存储 方法 不好
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode tmp = head;

        List<ListNode> list = new ArrayList<>();
        list.add(tmp);
        while (tmp.next != null){
            list.add(tmp.next);
            tmp = tmp.next;
        }
        if(n > list.size()){
            return null;
        }

        int delIdx = list.size() - n;
        ListNode delNode = list.get(delIdx);
        if(delIdx == 0){//如果是第一位
            return delNode.next;
        }

        ListNode pre = list.get(delIdx - 1);
        if(n == 1){
            //删除的最后一位
            pre.next = null;
        }else {
            ListNode next = list.get(delIdx + 1);
            pre.next = next;
        }
        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return ""+val;
        }
    }
}
